﻿#include <iostream>
#include <vector>



using namespace std;


/*
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]


示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
*/



 struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
 
 class Solution {
 public:
	 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		 if (l1 == NULL) return l2;
		 if (l2 == NULL) return l1;
		 ListNode* ans = NULL; ListNode* p = NULL;
		 while (l1 != NULL && l2 != NULL) {
			 if (l1->val <= l2->val) {
				 if (p == NULL || ans == NULL) {
					 ans = l1; p = l1;
				 }
				 else {
					 p->next = l1; p = p->next;
				 }

				 l1 = l1->next;
			 }
			 else {
				 if (p == NULL || ans == NULL) {
					 ans = l2; p = l2;
				 }
				 else {
					 p->next = l2; p = p->next;
				 }

				 l2 = l2->next;
			 }
		 }
		 ListNode* one = l1;
		 if (l2 != NULL) { one = l2; }
		 while (one != NULL) {
			 p->next = one;
			 one = one->next; p = p->next;
		 }

		 return ans;
	 }
 };


//
//int main() {
//
//
//
//
//
//	return 0;
//}